package training.day05;//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
// 有效字符串需满足：
//
//
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
//
//
//
//
// 示例 1：
//
//
//输入：s = "()"
//输出：true
//
//
// 示例 2：
//
//
//输入：s = "()[]{}"
//输出：true
//
//
// 示例 3：
//
//
//输入：s = "(]"
//输出：false
//
//
// 示例 4：
//
//
//输入：s = "([)]"
//输出：false
//
//
// 示例 5：
//
//
//输入：s = "{[]}"
//输出：true
//
//
//
// 提示：
//
//
// 1 <= s.length <= 104
// s 仅由括号 '()[]{}' 组成
//
// Related Topics 栈 字符串
// 👍 2539 👎 0


import java.util.*;

//leetcode submit region begin(Prohibit modification and deletion)
public class L20 {

    public static void main(String[] args) {

    }

    public static boolean isValid(String s) {
        Deque<Integer> deque = new ArrayDeque<Integer>();
        String push = "({[";
        int[] m = {')','}',']'};
        for (char c : s.toCharArray()) {
            int i = -1;
            if((i = push.indexOf(c)) > -1){
                deque.offerFirst(i);
            }else {
                Integer character = deque.pollFirst();
                if(character == null || m[character] != c){
                    return false;
                }
            }
        }
        return deque.isEmpty();
    }
}
//leetcode submit region end(Prohibit modification and deletion)
